1. Field of the Invention
The present invention relates to setting contents of memory for initializing data structures; and, in particular, to increasing efficiency by issuing a single command to set an arbitrary state in an arbitrary portion of memory using a memory controller.
2. Description of the Related Art
Networks of general purpose computer systems connected by external communication links are well known. The networks often include one or more network devices that facilitate the passage of information between the computer systems. A network node is a network device or computer system connected by the communication links.
Routers and switches are network devices that determine which communication link or links to employ to support the progress of data packets through the network. Routers and switches can employ software executed by a general purpose processor, called a central processing unit (CPU), or can employ special purpose hardware, or can employ some combination to make these determinations and forward the data packets from one communication link to another.
While the use of hardware causes data packets to be processed extremely quickly, there are drawbacks in flexibility. As communications protocols evolve through subsequent versions and as new protocols emerge, the network devices that rely on hardware become obsolete and have to ignore the new protocols or else be replaced. As a consequence, many network devices, such as routers, which forward packets across heterogeneous data link networks, include a CPU that operates according to an instruction set (software) that can be modified as protocols change. The software set constitutes a networking operating system, such as the Cisco Internet Operating System (IOS) available from Cisco Systems of San Jose, Calif.
Software executed operations in a CPU proceed more slowly than hardware executed operations, so there is a tradeoff between flexibility and speed in the design and implementation of network devices.
The throughput of many current routers is limited by the processing capacity of the CPU, i.e., the router performance is said to be CPU limited. To improve throughput of such routers, it is desirable to relieve the CPU load and replace some of the software functionality in the operating system with hardware functionality, without losing the flexibility to adapt to evolving protocols.
A very common routine that is called by a network operating system is a function to set each element in an array of data structure elements in memory with an initial value, i.e., to “initialize” the data structure array. In IOS, this function is provided by the software routine memset. When memset is called, an instruction is executed by the CPU for each location in memory. For example, to allocate memory for a hash table with 4000 entries, which is used to associate data packets with data flows and corresponding routing parameters, memset causes the CPU to issue 4000 store instructions for main memory, which is used as input and output memory (IOMEM) for storing input data and output data. Store instructions for IOMEM are sent directly to a parallel communication channel (a “bus” described in more detail in a later section) connecting the CPU to a memory controller (also described in more detail in a later section) for exchanging data with main memory. Thus, 4000 store instructions are sent over the bus to the memory controller. Each store instruction involves a burst of data involving several clock cycles on the bus. For example, in a Cisco 7200 Series router available from Cisco Systems, using a CPU Architecture from MIPS Technologies, Inc. of Mountain View, Calif., each data burst involves up to 40 bytes and 5 clock cycles on a fast device bus (FDB) connection between the CPU and a memory controller. Therefore, the 4000 store instructions can consume 20,000 cycles on the bus. The CPU and bus resources consumed to perform the memset operation are preferably utilized to perform other IOS functions.
In some start-up (“boot-strap,” or “boot”) operations, a CPU issues a single command to initialize memory. However, such operations typically initialize all memory with a preset value, such as all zeros. Similarly, some display controllers initialize all memory location indicating picture element (pixel) values to a preset value, e.g., representing a blue or black screen. These operations are not capable of setting an arbitrary section of memory, like 4000 hash table entries, to an arbitrary value that is determined by the programmable instruction set.
In one approach, a direct memory access (DMA) controller could be used to move data from a constant address to a target memory array. However, this approach requires the CPU either to wait and repeatedly poll the DMA for the status of the operation, or to wait for an interrupt sent by the DMA, before proceeding with usage of the initialized array in memory. Polling consumes multiple CPU and bus cycles that are preferably utilized for other IOS functions. Processing interrupts consumes CPU resources to switch the context of the CPU with a stack of instructions and data in memory. In addition, existing DMA controllers perform a memory read in addition to a memory write for every store instruction. Therefore, using a DMA controller to initialize 4000 entries in a hash table consumes further system resources to not only, write 4000 entries, but also to read 4000 entries, in addition to consuming resources to poll or process interrupts. Thus, the approaches using a DMA controller consume system resources that are preferably utilized for other IOS processing.
Based on the foregoing, there is a clear need for techniques to initialize blocks of memory with an arbitrary value, while reducing the number of CPU instructions, or reducing the amount of bus traffic, or reducing the burden on the CPU to determine when the initialization is complete, or some combination of these reductions.
The approaches described in this section could be pursued, but are not necessarily approaches that have been previously conceived or pursued. Therefore, unless otherwise indicated herein, the approaches described in this section are not to be considered prior art to the claims in this application merely due to the presence of these approaches in this background section.